package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class _200_NumberOfIslands {
    public static void main(String[] args) {
        Solution solution = new _200_NumberOfIslands().new Solution();
        char[][] grid = new char[][]{
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'},
        };
        int i = solution.numIslands(grid);
        System.out.println(i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) return 0;

            int nr = grid.length;
            int nc = grid[0].length;
            int res = 0;
            int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

            for (int r = 0; r < nr; r++) {
                for (int c = 0; c < nc; c++) {
                    if (grid[r][c] == '1') {
                        res++;
                        grid[r][c] = '0';
                        Queue<Integer> neighbors = new LinkedList<>();
                        neighbors.add(r * nc + c);
                        while (!neighbors.isEmpty()) {
                            int id = neighbors.peek();
                            neighbors.remove();
                            int row = id / nc, col = id % nc;
                            for (int k = 0; k < 4; k++) {
                                int newRow = row + dirs[k][0], newCol = col + dirs[k][1];
                                if (newRow >= 0 && newRow < nr && newCol >= 0 && newCol < nc && grid[newRow][newCol] == '1') {
                                    grid[newRow][newCol] = '0';
                                    neighbors.add(newRow * nc + newCol);

                                }
                            }
                        }
                    }
                }
            }
            return res;
        }
    }

    // 深度优先搜索
    class Solution1 {
        int nr, nc;

        private void dfs(char[][] grid, int r, int c) {
            if (r < 0 || r >= nr || c < 0 || c >= nc || grid[r][c] == '0') {
                return;
            }
            grid[r][c] = '0';
            dfs(grid, r - 1, c);
            dfs(grid, r + 1, c);
            dfs(grid, r, c - 1);
            dfs(grid, r, c + 1);
        }

        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) return 0;
            nr = grid.length;
            nc = grid[0].length;
            int res = 0;
            for (int r = 0; r < nr; r++) {
                for (int c = 0; c < nc; c++) {
                    if (grid[r][c] == '1') {
                        res++;
                        dfs(grid, r, c);
                    }
                }
            }
            return res;
        }
    }

    // 广度优先搜索
    class Solution2 {
        public int numIslands(char[][] grid) {
            if (grid == null || grid[0].length == 0) return 0;

            int nr = grid.length;
            int nc = grid[0].length;
            int res = 0;
            int[][] dirs = new int[][]{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

            for (int r = 0; r < nr; r++) {
                for (int c = 0; c < nc; c++) {
                    if (grid[r][c] == '1') {
                        res++;
                        grid[r][c] = '0';
                        Queue<Integer> neighbors = new LinkedList<>();
                        neighbors.add(r * nc + c);
                        while (!neighbors.isEmpty()) {
                            int id = neighbors.peek();
                            neighbors.remove();
                            int row = id / nc;
                            int col = id % nc;
                            for (int i = 0; i < 4; i++) {
                                int newRow = row + dirs[i][0], newCol = col + dirs[i][1];
                                if (newRow >= 0 && newRow < nr && newCol >= 0 && newCol < nc && grid[newRow][newCol] == '1') {
                                    grid[newRow][newCol] = '0';
                                    neighbors.add(newRow * nc + newCol);
                                }
                            }
                        }
                    }
                }
            }
            return res;
        }
    }

    // 并查集
    class Solution3 {
        public int numIslands(char[][] grid) {
            UF uf = new UF(grid);
            int m = grid.length, n = grid[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        if (i >= 1 && grid[i - 1][j] == '1') {
                            uf.union(i * n + j, (i - 1) * n + j);
                        }
                        if (j >= 1 && grid[i][j - 1] == '1') {
                            uf.union(i * n + j, i * n + j - 1);
                        }
                    }
                }
            }
            return uf.getCount();
        }

        class UF {
            int count;
            int[] parent;
            int[] size;

            public UF(char[][] grid) {
                int m = grid.length;
                int n = grid[0].length;

                count = 0;
                parent = new int[m * n];
                size = new int[m * n];

                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (grid[i][j] == '1') {
                            parent[i * n + j] = i * n + j;
                            size[i * n + j] = 1;
                            count++;
                        }
                    }
                }
            }

            public int find(int x) {
                while (parent[x] != x) {
                    x = parent[x];
                }
                return x;
            }

            public void union(int x, int y) {
                int rootx = find(x);
                int rooty = find(y);

                if (rootx != rooty) {
                    if (size[x] > size[y]) {
                        parent[rooty] = rootx;
                        size[rootx] += size[rooty];
                    } else {
                        parent[rootx] = rooty;
                        size[rooty] += size[rootx];
                    }
                    count--;
                }
            }

            public int getCount() {
                return count;
            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}